This invention relates to exponentiation circuits and methods, and more particularly to Montgomery exponentiation circuits and methods.
Montgomery multiplication is widely used to perform modular multiplication. Modular multiplication is widely used in encryption/decryption, authentication, key distribution and many other applications. Montgomery multiplication also may be used for the basis for Montgomery exponentiation, which also is widely used in the above-described and other applications.
Montgomery multiplication and exponentiation are described in U.S. Pat. No. 6,185,596 to Hadad et al. entitled Apparatus and Method for Modular Multiplication and Exponentiation Based on Montgomery Multiplication; U.S. Pat. No. 6,061,706 to Gai et al. entitled Systolic Linear-Array Modular Multiplier with Pipeline Processing Elements; U.S. Pat. No. 6,085,210 to Buer entitled High-Speed Modular Exponentiator and Multiplier; U.S. Pat. No. 5,513,133 to Cressel et al. entitled Compact Microelectronic Device for Performing Modular Multiplication and Exponentiation Over Large Numbers; and European Patent Application 0 656 709 A2 to Yamamoto et al. entitled Encryption Device and Apparatus for Encryption/Decryption Based on the Montgomery Method Using Efficient Modular Multiplication. Montgomery multiplication and exponentiation also are described in publications by Gutub et al. entitled An Expandable Montgomery Modular Multiplication Processor, Eleventh International Conference on Microelectronics, Nov. 22-24, 1999, pp. 173-176; Tenca et al. entitled A Scalable Architecture for Montgomery Multiplication, First International Workshop, Cryptographic Hardware and Embedded Systems, Lecture Notes on Computer Science, Vol. 1717, 1999, pp. 94-108; and Freking et al. entitled Montgomery Modular Multiplication and Exponentiation in the Residue Number System, Conference Record of the Thirty-Third Asilomar Conference Signals, Systems, and Computers, Vol. 2, 1999, pp. 1312-1316. The disclosure of all of these references is hereby incorporated herein in their entirety as if set forth fully herein.
Montgomery exponentiation often is used with large numbers. Accordingly, it may be desirable to accelerate Montgomery exponentiation so that rapid encryption/decryption, authentication, key management and/or other applications may be provided.
Embodiments of the invention provide Montgomery exponentiators and methods that modulo exponentiate a generator (g) to a power of an exponent (e). Embodiments of Montgomery exponentiators and methods include a first multiplier that is configured to repeatedly square a residue of the generator, to produce a series of first multiplier output values at a first multiplier output. A second multiplier is configured to multiply selected ones of the series of first multiplier output values that correspond to a bit of the exponent that is a predetermined binary value, such as binary one, by a partial result, to produce a series of second multiplier output values at a second multiplier output. By providing two multipliers that are serially coupled as described above, Montgomery exponentiation can be accelerated.
Montgomery exponentiators and methods according to other embodiments of the invention include a first register that is coupled to the second multiplier output, and is configured to serially store the series of second multiplier output values, to thereby provide the partial result. A second register is coupled to the first multiplier output, and is configured to serially store the series of first multiplier output values, and to serially provide the series of first multiplier values to the first and second multipliers. In yet other embodiments, the first register is configured to be initialized to the first binary value, and the second register is further configured to be initialized to the residue of the generator.
Montgomery exponentiators and methods according to other embodiments of the present invention include a first multiplier that is configured to be responsive to a residue of the generator and that includes a first multiplier output. A second multiplier is configured to be responsive to the first multiplier output, and includes a second multiplier output. In other embodiments, a first register is coupled to the second multiplier output, and the second multiplier output is also responsive to the first register. A second register is coupled to the first multiplier output, and the first multiplier is further responsive to the second register. The second multiplier is responsive to the first multiplier output via the second register. In still other embodiments, a controller also is provided that is configured to cause the first multiplier to square contents of the second register, and to cause the second multiplier to multiply the contents of the second register by contents of the first register if a selected bit of the exponent is a predetermined binary value, such as binary one, and to refrain from multiplying the contents of the second register by the contents of the first register if the selected bit of the exponent is not the predetermined binary value.
In any of the above-described embodiments, conventional Montgomery multipliers may be used for the first and second multipliers. However, according to other embodiments of the invention, embodiments of Montgomery multipliers may be used that can provide accelerated Montgomery multiplication using plural multipliers. These embodiments of the invention use Montgomery multipliers and methods that modular multiply a residue multiplicand by a residue multiplier to obtain a residue product. Embodiments of Montgomery multipliers and methods include a scalar multiplier, a first vector multiplier and a second vector multiplier. A controller is configured to control the scalar multiplier, the first vector multiplier and the second vector multiplier, to overlap scalar multiplies using a selected digit of the multiplier and vector multiplies using a modulus and the multiplicand. It will be understood that as used herein, digit refers to a number place in any base number system, including decimal, hexidecimal and binary. The latency of Montgomery multiplication thereby can be reduced to nearly the latency of a single scalar multiplication.
The Montgomery multipliers and methods according to other embodiments of the invention include a scalar multiplier that is configured to multiply a least significant digit of the multiplicand by a first selected digit of the multiplier, to produce a scalar multiplier output. A first vector multiplier is configured to multiply the scalar multiplier output by a modulus, to produce a first vector multiplier output. A second vector multiplier is configured to multiply a second selected digit of the multiplier by the multiplicand, to produce a second vector multiplier output. An accumulator is configured to add the first vector multiplier output and the second vector multiplier output, to produce a product output. The first selected digit of the multiplier preferably is a next more significant digit of the multiplier, relative to the first selected digit of the multiplier.
In other embodiments of the invention, the scalar multiplier is further configured to multiply the least significant digit of the multiplicand by the first selected digit of the multiplier and by one over (i.e., divided by) a negative of a least significant digit of the modulus, to produce the scalar multiplier output. In yet other embodiments, a first multiplexer also may be provided that is configured to multiplex the least significant digit of the multiplicand and one over the negative of the least significant digit of the modulus into the scalar multiplier.
In still other embodiments of the invention, a first feedback path is configured to feed the scalar multiplier output back into the scalar multiplier. A second feedback path is configured to feed the product output into the scalar multiplier. A summer is configured to sum the scalar multiplier output and the product output from the respective first and second feedback paths and to provide the sum of the scalar multiplier output and the product output to the scalar multiplier. A second multiplexer also is provided that is configured to multiplex the first selected digit of the multiplier and the sum of the scalar multiplier output and the product output into the scalar multiplier. A first register is coupled between the scalar multiplier output and the first vector multiplier and a second register is coupled between the product output and the second feedback path. Accordingly, latency in Montgomery multiplication can be reduced.